package com.xxd.algo.newcode.base01.class05;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Code03_TreeMaxWidth {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }


    public static int process(Node head) {
        if (head == null) {
            return 0;
        }

        Queue<Node> queue = new LinkedList<>();
        Map<Node, Integer> levelMap = new HashMap<>();
        queue.add(head);
        levelMap.put(head, 1);
        int curNodes = 0;
        int curLevel = 1;
        int max = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            head = queue.poll();
            int level = levelMap.get(head);
            System.out.print("Node = " + head.value + " Level = " + level);
            if (level == curLevel) {
                curNodes++;
            } else {
                // 能进入这个分支，只有说是 下一层的 第一个节点，才能进来结算上一层的信息
                // 结算当前层和之前层的最大值
                max = Math.max(max, curNodes);
                curLevel++;
                curNodes = 1;
            }
            System.out.println("  curNodes = " + curNodes);
            if (head.left != null) {
                queue.add(head.left);
                levelMap.put(head.left, level + 1);
            }

            if (head.right != null) {
                queue.add(head.right);
                levelMap.put(head.right, level + 1);
            }
        }

        max = Math.max(max, curNodes);

        return max;
    }

    public static int getMaxWidth(Node head) {
        if (head == null) {
            return 0;
        }
        int maxWidth = 0;
        int curWidth = 0;
        // 目前的层数
        int curLevel = 0;
        // node 所在的层数
        HashMap<Node, Integer> levelMap = new HashMap<>();
        levelMap.put(head, 1);
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(head);
        Node node = null;
        Node left = null;
        Node right = null;
        while (!queue.isEmpty()) {
            node = queue.poll();
            left = node.left;
            right = node.right;
            if (left != null) {
                levelMap.put(left, levelMap.get(node) + 1);
                queue.add(left);
            }
            if (right != null) {
                levelMap.put(right, levelMap.get(node) + 1);
                queue.add(right);
            }
            if (levelMap.get(node) > curLevel) {
                curWidth = 1;
                curLevel = levelMap.get(node);
            } else {
                curWidth++;
            }
            maxWidth = Math.max(maxWidth, curWidth);
        }
        return maxWidth;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        System.out.println(getMaxWidth(head));
        System.out.println(process(head));
    }

}
